首先是 700. Search in a Binary Search Tree (easy)
https://leetcode.com/problems/search-in-a-binary-search-tree/

在BST當中找出一個node的val與題目所提供的val相同的node點。

基本題、直接recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return
        if root.val == val:
            return root
        elif val > root.val:
            return self.searchBST(root.right,val)
        else:
            return self.searchBST(root.left,val)
        

再來是 733. Flood Fill (easy)
https://leetcode.com/problems/flood-fill/

首先他會給一個matrix，然後指定一個座標，要把該座標以及四周跟它有連結且值相同的座標變成相同的"color"

想法：

1. dfs
2. 設限制條件(邊界、顏色不相同、顏色已經是color的)return
3. 把與指定座標的值相同的座標的值改成color
4. dfs四個方位

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        L,W = len(image),len(image[0]) #長寬
        movement = [[0,1],[1,0],[0,-1],[-1,0]]
        record  = image[sr][sc]
        # print(color)
        def dfs(x,y):
            if x<0 or x==L or y<0 or y==W or image[x][y] == color:
                return
            if image[x][y] == record:
                image[x][y] = color
                dfs(x+1,y)
                dfs(x-1,y)
                dfs(x,y+1)
                dfs(x,y-1)

        dfs(sr,sc)
        image[sr][sc] = color
        return image
            

再來是 235. Lowest Common Ancestor of a Binary Search Tree (medium)
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

給一個BST，給兩個值為p跟q，找出p跟q最接近的共同祖節點(LCA)
想法1：

1. 題目有說 p跟q 必定存在，加上又是bst，不用擔心搜尋不到的狀況
2. 找出p跟q的根至自身的所有節點
3. 從開始的地方開始比對，找出開始分岔的上一個節點就是答案

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def find(root,path,target):
            if root.val == target.val:
                return path + [root.val]
            elif root.val < target.val:
                path.append(root.val)
                return find(root.right,path,target)
            elif root.val > target.val:
                path.append(root.val)
                return find(root.left,path,target)
        pPath = find(root,[],p)
        qPath = find(root,[],q)
        L = min(len(pPath),len(qPath))
        print(pPath,qPath)
        for i in range(0,L,1):
            if pPath[i] != qPath[i]:
                return TreeNode(pPath[i-1])
        if len(pPath)<len(qPath):
            return TreeNode(pPath[-1])
        return TreeNode(qPath[-1])

但後來參考了別人寫法，其實有一個更簡單的想法：
q跟p既然依訂有共同祖節點的話，那只要找到一個root.val夾在p跟q中間，那它就一定是共同祖節點。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        #找出誰的值大誰的值小，因為這是BST，所以是有序的
        if p.val < q.val:
            min_val = p.val
            max_val = q.val
        else:
            min_val = q.val
            max_val = p.val

        while True:
            if min_val <= root.val <= max_val:#若root的val恰好在中間，則必為共同祖節點
                return root
            elif max_val < root.val:#max比root小，則必在root的左邊
                root = root.left
            else:#反之亦然
                root = root.right

以上為今天的練習感謝大家